package BackTrack.Medium;

import com.sun.source.tree.Tree;

import java.util.*;

public class LC0017 {
    List<String> res = new ArrayList<>();
    TreeMap<Integer, Character[]> numberLetterMap = new TreeMap<>();

    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return res;

        numberLetterMap.put(2, new Character[]{'a', 'b', 'c'});
        numberLetterMap.put(3, new Character[]{'d', 'e', 'f'});
        numberLetterMap.put(4, new Character[]{'g', 'h', 'i'});
        numberLetterMap.put(5, new Character[]{'j', 'k', 'l'});
        numberLetterMap.put(6, new Character[]{'m', 'n', 'o'});
        numberLetterMap.put(7, new Character[]{'p', 'q', 'r', 's'});
        numberLetterMap.put(8, new Character[]{'t', 'u', 'v'});
        numberLetterMap.put(9, new Character[]{'w', 'x', 'y', 'z'});

        backTrack(digits, null);
        return res;
    }

    private void backTrack(String digits, LinkedList<Character> path) {
        if (path == null) path = new LinkedList<>();
        if (path.size() == digits.length()) {
            char[] charArray = new char[path.size()];
            for (int i = 0; i < path.size(); i++) charArray[i] = path.get(i);
            res.add(new String(charArray));
            return;
        }

        Character[] choices = numberLetterMap.get(digits.charAt(path.size()) - '0');
        for (char ch : choices) {
            path.add(ch);
            backTrack(digits, path);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        String digits = "23";
        LC0017 solution = new LC0017();
        System.out.println(solution.letterCombinations(digits));
    }
}
